package com.yan;

import java.util.ArrayDeque;
import java.util.Stack;

/**
 * 输入: [7,1,5,3,6,4]
 * 输出: 5
 * 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
 *      注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author: yanheng
 * @date: 2020/6/4
 */
public class StockMaxProfit {
    public int maxProfit(int[] prices) {
        int profit = 0;
        Stack<Integer> stack = new Stack();
        for (int p : prices) {
            if (!stack.isEmpty() && stack.peek() > p) {
                profit = Math.max(profit, stack.peek() - stack.firstElement());
                while (!stack.empty() && stack.peek() >= p) {
                    stack.pop();
                }
            }
            stack.push(p);
        }
        if (!stack.isEmpty()) {
            profit = Math.max(profit, stack.peek() - stack.firstElement());
        }
        return profit;
    }

    public static void main(String[] args) {
        int[] prices = new int[] {7,1,5,3,6,4};
        System.out.println(new StockMaxProfit().maxProfit(prices));
    }
}
